package 中等.滑动窗口;

/**
 * 给你一个整数数组 nums 和一个整数 k ，请你返回子数组内所有元素的乘积
 * 严格小于 k 的连续子数组的数目。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/subarray-product-less-than-k/
 */
public class 乘积小于K的子数组_713 {

    public static void main(String[] args) {

    }

    /**
     * 前缀和+二分查找+动态规划
     * 计算sum[0,i]=num[0]*num[1]*...num[i]，会整数溢出
     *
     * @param nums
     * @param k
     * @return
     */
    public int numSubarrayProductLessThanK(int[] nums, int k) {
        int ans = 0;

        return ans;
    }

    /**
     * 滑动窗口+动态规划
     * 以索引i结尾的符合条件个数为多少
     * 每次右指针向右移动一个位置，并且计算左右指针的乘积，左指针通过左右移动来确定，窗口小于k的最大值
     *
     * @param nums
     * @param k
     * @return
     */
    public int numSubarrayProductLessThanK2(int[] nums, int k) {
        // 特殊情况，数组中乘积最小为1
        if (k <= 1) return 0;
        int ans = 0;
        int left = 0, right = 0, sum = 1;
        while (right < nums.length) {
            sum *= nums[right];
            // 右边界向右移动一位后，sum增大，左指针一定是往右边移动，使得sum减小
            while (left <= right && sum >= k) {
                sum /= nums[left];
                left++;
            }
            // left-right=1时，nums[right]>=k，以right结尾的连续子数组乘积<k个数为0
            ans += right - left + 1;
            right++;
        }
        return ans;
    }

}
